#ifndef __CDS_AVL_H__
#define __CDS_AVL_H__

#include"cds_common.h"
#include<assert.h>
#ifdef __cplusplus
extern "C" {
#endif

//avl树节点
typedef struct _avl_node {
    struct _avl_node *parent; //父节点
    struct _avl_node *left;//左子节点
    struct _avl_node *right;//右子节点
    int height; //节点高度, 叶子节点的高度为0,NULL的高度为-1
} avl_node_t;

//生成key的函数类型
typedef unsigned long (*keygen_func_t)(avl_node_t * node );

//销毁数据的回调函数类型
typedef void (*destroy_func_t)(avl_node_t * node );

//遍历数据的回调函数类型
typedef void (*travel_func_t)(avl_node_t * node ); 

//avl树
typedef struct _avl_tree{
    avl_node_t * root;
    unsigned long size;
    keygen_func_t keygen_func;
} avl_tree_t;

//初始化avl树指针
#define AVL_TREE_INIT(tree,func) do{\
    tree->root = NULL;\
    tree->size = 0 ; \
    tree->keygen_func = func ;\
    assert(func);\
    }while(0)

//avl树的初始化值
#define AVL_TREE(func) ({\
    assert(func);\
    ((avl_tree_t){NULL,0,func});\
    })

//从avl树节点上获取用户的type类型数据结构的地址
#define avl_entry(ptr, type,member) container_of(ptr,type,member)

//获取avl树的节点数量
#define avl_size(tree) ((tree)->size)



//遍历avl树,中序遍历,即从小到大
#define avl_for_each(pos,tree) \
    for(pos = avl_first(tree->root); \
        pos;pos = avl_next(pos) ) 
        

//插入一个节点
avl_node_t * avl_insert(avl_tree_t * tree, avl_node_t * node);

//搜索
avl_node_t * avl_search(avl_tree_t * tree, unsigned long key);

//获得树根root的第一个节点
#define avl_first(root) ({\
    avl_node_t * _root = (root);\
    while(_root->left) _root = _root->left;\
    _root;})

//获得树根root的最后一个节点
#define avl_last(root) ({\
    avl_node_t * _root = (root);\
    while(_root->right) _root = _root->right;\
    _root; })

//下一个节点
avl_node_t * avl_next(avl_node_t * node );

//上一个节点
avl_node_t * avl_prev(avl_node_t * node ); 


//删除一个节点
void avl_del(avl_tree_t * tree, avl_node_t * node);

//遍历avl树
void avl_travel_middle(avl_tree_t * tree, travel_func_t travel );

//层次遍历avl树
void avl_travel_level(avl_tree_t * tree, travel_func_t travel );

//清空avl树
void avl_clear(avl_tree_t * tree ,destroy_func_t  destroy);

#ifdef __cplusplus
}
#endif
#endif //__CDS_AVL_H__
